package com.example.leetcode.trainingcamp.week6.Sunday;



/**
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 *
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 *
 * 示例 1:
 */
public class Offer04_06 {

    private boolean is = false;
    TreeNode result = null;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
      if (root == null) return null;
      dfs(root,p);
      return result;
    }


    public void dfs(TreeNode root,TreeNode p){
        if (root == null) return;
        dfs(root.left,p);
        if (is){
            result = root;
            is = false;
            return;
        }
        if (root == p){
            is = true;
        }
        dfs(root.right,p);
    }
}
